package xyz.scootaloo.oj.offer

import org.junit.Test

/**
 * @author flutterdash@qq.com
 * @since 2021/4/8 17:13
 */
class P04 {

    private fun findNumberIn2DArray(matrix: Array<IntArray>, target: Int): Boolean {
        val row = matrix.size; if (row == 0) return false
        val column = matrix[0].size; if (column == 0) return false
        if (target < matrix[0][0] || target > matrix[row - 1][column - 1])
            return false

        fun searchColumn(c: Int): Boolean {
            for (r in 0 until row)
                if (matrix[r][c] == target)
                    return true
            return false
        }

        for (c in 0 until column) {
            if (matrix[0][c] > target)
                break
            if (target >= matrix[0][c] && target <= matrix[row - 1][c])
                if (searchColumn(c)) return true
        }

        return false
    }

    @Test
    fun test0() {
        val input = arrayOf(
            intArrayOf(1, 4, 7, 11, 15),
            intArrayOf(2, 5, 8, 12, 19),
            intArrayOf(3, 6, 9, 16, 12),
            intArrayOf(10, 13, 14, 17, 24),
            intArrayOf(18, 21, 23, 26, 30),
        )
        val input1 = arrayOf(
            intArrayOf(-1, 3),
        )
        println(findNumberIn2DArray(input1, 3))
        println(findNumberIn2DArray(input, 5))
        println(findNumberIn2DArray(input, 20))
    }

}
